package huaweiod.first;

/**
 * HWOD机试真题 Java 实现【最多获得的短信条数】【2022.11 Q4 新题】
 */
public class A_2023_30_MaxShortMessage {

    public static int res = 0;

    public static int maxShortMessage1(int money, int[] message) {
        int dfs = dfs(message, money, 0);
        return res;
    }

    public static int dfs(int[] message, int money, int ans) {
        if (money < 1) {
            return ans;
        }
        for (int i = 0; i < message.length; i++) {
            if (money > i) {
                money = money - i - 1;
                ans = ans + message[i];
                int dfs = dfs(message, money, ans);
                if (dfs <= res) {
                    money = money + i + 1;
                    ans = ans - message[i];
                } else {
                    res = dfs;
                }
            }
        }
        return ans;
    }

    // 动态规划（完全背包问题）
    public static int maxShortMessage(int money, int[] message) {
        // i为物品，j为拥有的空间
        int[] dp = new int[money + 1];
        for (int i = 0; i <= message.length; i++) {
            for (int j = 0; j <= money; j++) {
                if (i > 0 && j > 0 && j >= i) {
                    dp[j] = Math.max(dp[j], dp[j - i] + message[i - 1]);
                }
            }
        }
        return dp[money];
    }

    public static void main(String[] args) {
        int[] message = {10, 20, 30, 40, 60};
        System.out.println(maxShortMessage(6, message));
        res = 0;
        int[] message1 = {10, 20, 30, 40, 60, 60, 70, 80, 90, 150};
        System.out.println(maxShortMessage(15, message1));
    }
}
